/* Copyright (c) 2006 by M Aamir Maniar
 * 
 * Permission is hereby granted, free of charge, to any person obtaining 
 * a copy of this software and associated documentation files (the 
 * "Software"), to deal in the Software without restriction, including 
 * without limitation the rights to use, copy, modify, merge, publish, 
 * distribute, sublicense, and/or sell copies of the Software, and to 
 * permit persons to whom the Software is furnished to do so, subject to 
 * the following conditions:
 * 
 * The above copyright notice and this permission notice shall be 
 * included in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 * 
 * */

namespace Generic.Algorithms.Sorting
{
    using System;
    using System.Collections.Generic;
    using System.Text;
    using Generic.Utils;

    public class MergeSortStrategy<T> : SortStrategy<T>
    {
        SortDirection _direction;

        public MergeSortStrategy()
        {
        }

        public MergeSortStrategy(IList<T> list)
            : base(list)
        {
        }

        public override void Sort(SortDirection sortDirection)
        {
            _direction = sortDirection;

            base.Sort(sortDirection);
            DoMergeSort(0, List.Count - 1);
        }

        private void DoMergeSort(int left, int right)
        {
            if (left < right)
            {
                int middle = (left + right) / 2;
                DoMergeSort(left, middle);
                DoMergeSort(middle+1, right);
                MergeLists(left, middle, right);
            }
        }

        private void MergeLists(int left, int middle, int right)
        {
            bool descending = (_direction == SortDirection.Descending) ? true : false;
            while ((middle+1 <= right) && (left <= middle))
            {
                if ((CompareTo(List[left], List[middle + 1]) < 0) ^ descending)
                {
                    left++;
                }
                else
                {
                    T item = List[middle + 1];

                    for (int index = middle; index >= left; index--)
                    {
                        List[index + 1] = List[index];
                    }

                    List[left] = item;
                    left++;
                    middle++;
                }
            }

        }

    }
}
